package com.lw.leetcode.dp.b;

/**
 * 931. 下降路径最小和
 *
 * @Author liw
 * @Date 2021/6/4 15:13
 * @Version 1.0
 */
public class MinFallingPathSum {
    public int minFallingPathSum(int[][] matrix) {
        int length = matrix.length;
        if (length == 1) {
            return matrix[0][0];
        }
        int limit = length - 1;
        for (int i = 1; i < length; i++) {
            int[] arr = matrix[i - 1];
            int[] arr2 = matrix[i];
            for (int j = 0; j < length; j++) {
                if (j == 0) {
                    arr2[0] += Math.min(arr[0], arr[1]);
                } else  if (j == limit) {
                    arr2[j] += Math.min(arr[j], arr[j - 1]);
                } else {
                    arr2[j] += Math.min(Math.min(arr[j], arr[j - 1]), arr[j + 1]);
                }
            }
        }
        int[] arr = matrix[limit];
        int min = arr[0];
        for (int i = 1; i < length; i++) {
            min = Math.min(min, arr[i]);
        }
        return min;
    }
}
